مسئلهی آتشسوزی در برره

مسئله برخی از نقاط روستای برره در حملهی دشمن فرضی آتش گرفتهاند! این آتش رفته رفته گسترش پیدا کرده و به نقاط دیگر نیز سرایت میکند. خرزو خان که تنها بازماندهی روستا در نبرد با دشمن فرضی است، تلاش میکند خود را برای نجات به تنها هلیکوپتر روستا برساند. روستا را به صورت شبکهای با ابعاد $ n times m $ در نظر بگیرد که برخی خانههای آن در آغاز آتش گرفتهاند و اگر خانهای در زمان $x$ آتش گرفته باشد، هشت خانهی مجاور آن در زمان $ x + k$ آتش خواهند گرفت و هرگز خاموش نمیشوند. حال اگر خرزو خان در نقطهی $s$ شبکه باشد، میتواند در هر ثانیه به یکی از چهار خانهی مجاور بالا، پایین، راست یا چپ خود برود و تلاش کند به نقطهی $t$ که هلیکوپتر در آن قرار دارد برسد. برنامهای بنویسید که کوتاهترین مسیر ممکن برای حرکت امن و بدون درگیری با آتش خرزو خان از نقطهی $s$ به نقطهی $t$ را مشخص کند. ادامه مطلب